
def search_first_occ(seq, pattern):
    found = False
    i = 0
    while i <= len(seq) - len(pattern) and not found:
        j = 0
        while j < len(pattern) and pattern[j] == seq[i + j]:
            j += 1
        if j == len(pattern):
            found = True
        else:
            i += 1
    if found:
        return i
    else:
        return -1

def search_all_occurrences(seq, pattern):
    res = []
    for i in range(len(seq) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and pattern[j] == seq[i + j]:
            j += 1
        if j == len(pattern):
            res.append(i)
    return res
class BoyerMoore:
    def __init__(self, alphabet, pattern):
        self.alphabet = alphabet
        self.pattern = pattern
        self.preprocess()

    def preprocess(self):
        self.process_bcr()
        self.process_gsr()

    def process_bcr(self):
        self.occ = {}
        for symb in self.alphabet:
            self.occ[symb] = -1
        for j in range(len(self.pattern)):
            c = self.pattern[j]
            self.occ[c] = j

    def process_gsr(self):
        self.f = [0] * (len(self.pattern) + 1)
        self.s = [0] * (len(self.pattern) + 1)
        i = len(self.pattern)
        j = len(self.pattern) + 1
        self.f[i] = j
        while i > 0:
            while j <= len(self.pattern) and self.pattern[i - 1] != self.pattern[j - 1]:
                if self.s[j] == 0:
                    self.s[j] = j - i
                j = self.f[j]
            i -= 1
            j -= 1
            self.f[i] = j
        j = self.f[0]
        for i in range(len(self.pattern)):
            if self.s[i] == 0:
                self.s[i] = j
            if i == j:
                j = self.f[j]

    def search_pattern(self, text):
        res = []
        i = 0
        while i <= len(text) - len(self.pattern):
            j = len(self.pattern) - 1
            while j >= 0 and self.pattern[j] == text[j + i]:
                j -= 1
            if j < 0:
                res.append(i)
                i += self.s[0]
            else:
                c = text[j + i]
                i += max(self.s[j + 1], j - self.occ[c])
        return res

def test_BoyerMoore():
    bm = BoyerMoore("ACTG", "ACCA")
    print(bm.search_pattern("ATAGAACCAATGAACCATGATGAACCATGGATACCCAACCACC"))

def overlap(s1, s2):
    maxov = min(len(s1), len(s2))
    for i in range(maxov, 0, -1):
        if s1[-i:] == s2[:i]:
            return i
    return 0

class Automata:
    def __init__(self, alphabet, pattern):
        self.numstates = len(pattern) + 1
        self.alphabet = alphabet
        self.transition_table = {}
        self.build_transition_table(pattern)

    def build_transition_table(self, pattern):
        for q in range(self.numstates):
            for a in self.alphabet:
                prefix = pattern[0:q] + a
                self.transition_table[(q, a)] = overlap(prefix, pattern)

    def print_automata(self):
        print("States:", self.numstates)
        print("Alphabet:", self.alphabet)
        print("Transition table:")
        for k in self.transition_table.keys():
            print(k[0], ",", k[1], " ->", self.transition_table[k])

    def next_state(self, current, symbol):
        return self.transition_table.get((current, symbol))

    def apply_seq(self, seq):
        q = 0
        res = [q]
        for c in seq:
            q = self.next_state(q, c)
            res.append(q)
        return res

    def occurrences_pattern(self, text):
        q = 0
        res = []
        for i in range(len(text)):
            q = self.next_state(q, text[i])
            if q == self.numstates - 1:
                res.append(i - self.numstates + 2)
        return res

def test_Automata():
    auto = Automata("ACGT", "ACA")
    auto.print_automata()
    print(auto.apply_seq("CACATGACATG"))
    print(auto.occurrences_pattern("CACATGACATG"))

def find_pattern_re(seq, pat):
    from re import search
    mo = search(pat, seq)
    if mo is not None:
        return mo.span()[0]
    else:
        return -1

def find_all_occurrences_re(seq, pat):
    from re import finditer
    mos = finditer(pat, seq)
    res = []
    for x in mos:
        res.append(x.span()[0])
    return res

def test_regex():
    seq = input("Input sequence:")
    pat = input("Input pattern (as a regular expression):")
    if not seq or not pat:
        print("Sequence or pattern cannot be empty.")
        return
    res = find_pattern_re(seq, pat)
    if res >= 0:
        print("Pattern found in position:", res)
    else:
        print("Pattern not found")
    all_res = find_all_occurrences_re(seq, pat)
    if len(all_res) > 0:
        print("Pattern found in positions:", all_res)
    else:
        print("Pattern not found")

def find_all_overlap(seq, pat):
    return find_all_occurrences_re(seq, "(?="+pat+")")

def validate_dna_re(seq):
    from re import search, IGNORECASE
    if search("[^ACTG]", seq, IGNORECASE) is not None:
        return False
    else:
        return True

def translate_codon_re(cod):
    import re
    aa_table = {
        "GC.": "A", "TG[TC]": "C", "GA[TC]": "D", "GA[AG]": "E",
        "TT[TC]": "F", "GG.": "G", "CA[TC]": "H", "AT[TCA]": "I",
        "AA[AG]": "K", "TT[AG]|CT.": "L", "ATG": "M", "AA[TC]": "N",
        "CC.": "P", "CA[AG]": "Q", "CG.|AG[AG]": "R", "TC.|AG[TC]": "S",
        "AC.": "T", "GT.": "V", "TGG": "W", "TA[TC]": "Y", "TA[AG]|TGA": "_"
    }
    for pattern, aa in aa_table.items():
        if re.search(pattern, cod):
            return aa
    return ""

def largest_protein_re(seq_prot):
    import re
    mos = re.finditer("M[^_]*_", seq_prot)
    sizem = 0
    lprot = ""
    for x in mos:
        ini = x.span()[0]
        fin = x.span()[1]
        s = fin - ini + 1
        if s > sizem:
            lprot = x.group()
            sizem = s
    return lprot

if __name__ == "__main__":
    seqDNA = "ATAGAATAGATAATAGTC"
    print(search_first_occ(seqDNA, "GAAT"))
    print(search_first_occ(seqDNA, "TATA"))
    print(search_all_occurrences(seqDNA, "AAT"))

    test_BoyerMoore()

    test_Automata()
    test_regex()

